In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One such protocol is MPLS (Multi Protocol Label Switching). MPLS is a protocol that is well known to the skilled reader and which is described in document “Multi Protocol Label Switching Architecture” which is available at the time of this writing in the file “rfc3031.txt” in the directory “rfc” of the domain “ietf.org” on the World Wide Web. According to MPLS, a complete path for a source-destination pair is established, and values required for forwarding a packet between adjacent routers in the path together with headers or “labels” are pre-pended to the packet. The labels are used to direct the packet to the correct interface and next hop. The labels precede the IP or other header allowing smaller outer headers.
The path for the source-destination pair, termed a Label Switched Path (LSP) can be established according to various different approaches. One such approach is Label Distribution Protocol (LDP) in which each router in the path sends its label to the next hop router on the path as determined from its IP routing table. Alternatively Resource Reservation Protocol (RSVP) can be invoked in which case, for example, a network administrator can engineer a path, providing strict source routing. In either case a Label Forwarding Information Base (LFIB) stores both the next-hop information for the LSP, together with the label required by the next hop.
For each LSP created, a forwarding equivalent class (FEC) is associated with the path specifying which packets are mapped to it.
A problem in data communication networks arises upon de-activation of a network component such as a link or a node either by component failure or by planned down time. In either case there is a period of disruption to the delivery of traffic and packets for destinations which were previously reached by traversing the deactivated component may be dropped. In many time-critical applications it is not sufficient for the routers to converge on the adjusted network in a normal way as this takes too much time. Accordingly one known solution in MPLS networks is to pre-compute and pre-signal a repair path using RSVP methods. Such an approach can, however, require network administrator configuration of the repair paths.
An alternative approach is described in “ip/ldp local protection” which is available at the time of this writing in the file “draft-atlas-ip-local-protect-00.txt” in the directory “pub/id” of the domain “watersprings.org” on the World Wide Web. According to the approach described in this document, a computing node computes both a “primary next-hop” for packets for a destination together with an “alternate next-hop”. The alternate next hop is used in the case of failure of the primary next hop (failure either of the next-hop node or the link to the next hop-node). The alternate next-hop can be another neighbor node whose own shortest path to the destination does not include the computing node. In another case the alternate next-hop is a “U-turn alternate” comprising a neighbor whose primary next hop is the computing node. And which has as its alternate next-hop a node whose shortest path does not include the computing node. However this approach can only redirect a packet over a maximum of two hops.
A further approach is described in co-pending patent application Ser. No. 10/976,076, filed 27 Oct. 2004 entitled “Method and Apparatus for Forwarding Data in a Data Communications Network” of George Swallow et al (“Swallow et al.”), the entire contents of which are incorporated by reference for all purposes as set fourth herein and discussed in more detail below.
According to the solution put forward in Swallow et al. a repairing node repairs around a failed component to a target node from which data will be forwarded to its destination. In particular a repairing node constructs an LSP to a node at the intersection of a first set of nodes reachable from the repairing node and a second set of nodes from which the target node is reachable without traversing the failed component.
Further solutions have also been proposed in the case of IP packets using, for example, link state protocols.
The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning tree rooted at any other node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network, each node sending it to each adjacent node. However no solutions are currently proposed for supporting multi-topology routing in the multi protocol switching (MPLS) forwarding environment.
As a result, when a data packet for a destination node arrives at a node (the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
One such solution is described in co-pending patent application Ser. No. 10/340,371, filed 9 Jan. 2003, entitled “Method and Apparatus for Constructing a Backup Route in a Data Communication Network” of Kevin Miles et al (“Miles et al”), the entire contents of which are incorporated by reference for all purposes as fully set forth herein. In this case a repairing node tunnels repair packets to a node at the intersection of the first and second sets of nodes.
When a link or a node fails and is subsequently repaired, or there is some other change to the network such as a change of link cost, the routers involved with the repaired part of the network then have to re-establish convergence. This is achieved by the router(s) advertising themselves or the change throughout the network area. However during topology change there will be a short period of time in which LSDBs, RIBs and, critically, FIBs across a network become inconsistent as information about a change is propagated through the network. Routes generated during this period of inconsistency may result in routing loops, which persist until the databases have converged (at which point there should be no loops, by definition). As an example, if a first node sends a packet to a destination node via a second node, comprising the optimum route according to the first node's SPF, a situation can arise where the second node, according to it's SPF (based on a different LSDB from that of the first node) determines that the best route to the destination node is via the first node and sends the packet back. The loop can happen where the first node, according to its LSDB believes that a link cost is lower than the second node does, according to its LSDB. This can continue indefinitely although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes. Re-convergence will typically take several hundred milliseconds and hence may cause disruption for periods greater than that originally caused by the failure.
Such a problem can be understood with reference to FIG. 1 and FIG. 2 which are illustrative network diagrams showing a network in which such a problem can arise. Referring to FIG. 1, a network designated generally 100 includes node A, B, C, E, F, G, H and a destination node B, reference numerals 102, 104, 106, 108, 110, 112, 114 and 116 respectively. Each of the nodes excepting node D is connected in sequence, ordered node H, G, F, E, C, A, B. Both of nodes B and H provide a route to destination node D. Each node includes forwarding information including an LFIB for MPLS forwarding. In particular nodes A, C, E, F, G have forwarding information shown at 118, 120, 122, 124, 126 respectively. Thus, for IP packets received at node A destined for node D, the next hop is node B and node B's label for D, Db is appended. For MPLS packets belonging to the FEC for destination D the LFIB contains next hop B and, once again, B's label Db. For example where node A receives an MPLS packet from node C with A's ingress label for D, Da, node A replaces the label with Db and forwards it to next hop node B. Similarly, node C has, as next hop, node A and label Da for IP packets destined for node D and MPLS packets in the corresponding FEC. Node E has label Dc and next hop C and node F has label De and next hop node E. However the shortest route from node G to node D is via node H as a result of which node G has next hop node H and label Dh.
Referring now to FIG. 2, which shows the network topology following failure of node B, it will be seen that node A implements a repair path 200 to node D which can be any appropriate repair path for example of the type described above in Swallow et al or Miles et al. As a result the forwarding information at node A ensures implementation of the appropriate repair strategy for packets destined for node D. The forwarding information for the remaining nodes remains the same such that all packets arriving at node A will be forwarded to node D according to the repair mechanism invoked. However, once the network converges on the revised topology it will be seen that the forwarding information for each of nodes A, C, E, E, G, H will be to the next hop in the direction of node H as node D is now only reachable from node H. Accordingly, if different nodes update their forwarding information at different times then loops can arise. For example if node E updates its forwarding information before node F then it will forward packets destined for node D towards node F whereas node F will forward packets destined for node D to node E creating a loop.
A solution for avoiding loops during a routing transition is described in co-pending patent application Ser. No. 10/442,589, filed May 20, 2003, entitled “Method and Apparatus for Constructing a Transition Route in a Data Communications Network” of Stewart Bryant et al. (“Bryant et al”), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to the solution put forward in Bryant, when a network component fails, upstream nodes construct transition routes to destinations which would otherwise be reachable via the failed component. The transition routes are constructed by tunneling packets for the destination node to an intermediate node in an intersection of a first set of nodes reachable from the repairing node without traversing the failed component and a second set of nodes from which the destination node is reachable without traversing the first component. Although this is a very effective solution, it requires installation of a large number of tunnels.
Another solution is described in co-pending patent application Ser. No. 10/685,622 filed 14 Oct. 2003 entitled “Method and Apparatus for Generating Routing Information in a Data Communication Network” of Stefano Previdi et al (“Previdi et al)”, the entire contents of which are incorporated by reference for all purposes as fully set forth herein. According to the solution set forth in Previdi et al, the furthest nodes upstream of a failed component and which are affected by the change are identified. Then updating of the FIBs of each node can be carried out sequentially using this knowledge to ensure that tables are updated in order from the furthest affected router such that loops do not occur. However this approach can be complex, for example in the presence of Shared Risk Link Groups (SRLG).